Constrained optimum tree (COT) and constrained optimum path (COP)problems arise in many real-life applications and are ubiquitous in communicationnetworks. They have been traditionally approached by dedicated algorithms, whichare often hard to extend with side constraints and to apply widely. This paper pro-poses a constraint-based local search framework for COT/COP applications, bring-ing the compositionality, reuse, and extensibility at the core of constraint-based localsearch and constraint programming systems. The modeling contribution is the abil-ity to express compositional models for various COT/COP applications at a highlevel of abstraction, while cleanly separating the model and the search procedure.The main technical contribution is a connected neighborhood based on rooted span-ning trees to find high-quality solutions to COP problems. This framework is appliedto some COT/COP problems, e.g., the quorumcast routing problem, the edge-disjointpaths problem, and the routing and wavelength assignment with delay side constraintsproblem. Computational results show the potential importance of the approach.
展开▼
